home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11892 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.5 KB
  1. Path: EU.net!sun4nl!xs4all!falstaff
  2. From: falstaff@xs4all.nl (Falstaff)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: "Best fit" algorithm (help)
  5. Date: 27 Mar 1996 12:11:25 GMT
  6. Organization: XS4ALL, networking for the masses
  7. Message-ID: <4jbb9d$g14@news.xs4all.nl>
  8. References: <APC&7'0'22b6b83'874@peg.apc.org> <4j9215INNgbo@keats.ugrad.cs.ubc.ca>
  9. NNTP-Posting-Host: xs1.xs4all.nl
  10. X-Newsreader: NN version 6.5.0 #666 (NOV)
  11.  
  12. c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) writes:
  13.  
  14. > >I am looking for a "best fit" algorithm. 
  15. > >The problem I have is very similar to finding the best way of fitting the 
  16. > >maximum number of songs on (say) 45 minute tape.
  17.  
  18. >Assuming that you don't care _which_ songs go on the tape, try a ``greedy''
  19. >approach. Always add to the tape a song which will leave the most free space.
  20.  
  21. >This means starting with the smallest one, and adding the next bigger one and
  22. >so on. This should yield an optimal solution for the constraint of maximizing
  23. >the number of songs that go on the tape. It won't minimize the left-over space,
  24. >however.
  25.  
  26. Hmmm.  I think the user wants to minimize just that (unused space).
  27. To do that, you should pick the *largest* item that will still fit.
  28. Knuth (?) has proof that this is guaranteed to use less than twice
  29. the minimum possible space to fit all items, and *likely* to use
  30. much less than that maximum.
  31.  
  32. Frank
  33. --
  34. The famous GIICM now on line:  http://www.xs4all.nl/~falstaff/GIICM.html
  35. ------------------------------------------------------------------------
  36. Frank A. Vorstenbosch        +31-(70)-355 5241        falstaff@xs4all.nl
  37.